package com.success.airbnb;

import org.junit.Test;

import java.util.*;

/**
 * Desc: 2018.12.19
 * lj - airbnb
 * leetCode: https://leetcode.com/problems/word-search-ii/
 * Create by John Jiang On 2018/12/20
 */
public class WordSearchII {

    public List<String> findWords(char[][] board, String[] words) {
        TrieTree root = generate(words);
        Set<String> set = new HashSet<>();
        int n = board.length;
        int m = board[0].length;
        boolean[][] access = new boolean[n][m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                access[i][j] = true;
            }
        }
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[i].length; j++) {
                search(board, root, i, j, set, access);
            }
        }
        return new ArrayList<>(set);
    }

    private void search(char[][] board, final TrieTree root, int i, int j, final Set<String> result, boolean[][] access) {
        int c = board[i][j] - 'a';
        if (root.next[c] == null) {
            return;
        }
        if (root.next[c].word != null) {
            result.add(root.next[c].word);
        }
        access[i][j] = false;
        // up
        if (i > 0 && access[i - 1][j]) {
            search(board, root.next[c], i - 1, j, result, access);
        }
        // down
        if (i < board.length - 1 && access[i + 1][j]) {
            search(board, root.next[c], i + 1, j , result, access);
        }
        // left
        if (j > 0 && access[i][j - 1]) {
            search(board, root.next[c], i, j - 1, result, access);
        }
        // right
        if (j < board[i].length - 1 && access[i][j + 1]) {
            search(board, root.next[c], i, j + 1, result, access);
        }
        access[i][j] = true;
    }

    private TrieTree generate(String[] words) {
        TrieTree root = new TrieTree();
        for (String word : words) {
            TrieTree p = root;
            for (char c : word.toCharArray()) {
                if (p.next[c - 'a'] == null) {
                    p.next[c - 'a'] = new TrieTree();
                }
                p = p.next[c - 'a'];
            }
            p.word = word;
        }
        return root;
    }

    static class TrieTree {
        TrieTree[] next;
        String word;

        public TrieTree() {
            next = new TrieTree[26];
        }
    }

    @Test
    public void test() {
        String[] words = {"oath","pea","eat","rain"};
        char[][] board = {"oaan".toCharArray(), "etae".toCharArray(), "ihkr".toCharArray(), "iflv".toCharArray()} ;
        System.out.println(findWords(board, words));
    }

}
